// Copyright 2013 By Jshi. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

// Implement Heap Sort
// http://en.wikipedia.org/wiki/Heap_sort
package sort

import . "sort"

// siftUp implements the heap property on data[Top, last]
func siftUp(data Interface, top, last int) {
	parent := int((last+1)/2) - 1

	for parent >= top && data.Less(parent, last) {
		data.Swap(parent, last)
		last = parent
		parent = int((last+1)/2) - 1
	}
}

// siftDown implements the heap property on data[Top, last]
func siftDown(data Interface, top, last int) {
	for {
		left := 2*top + 1

		if left > last {
			break
		}

		largger, right := left, left+1
		if right <= last && data.Less(left, right) {
			largger = right
		}

		if data.Less(top, largger) {
			data.Swap(top, largger)
			top = largger
		} else {
			break
		}
	}
}

// heap sort implement.
func heapSort(data Interface, lo, hi int) {
	top, last := lo, hi
	// Build greatest heap.
	for i := top; i < last; i++ {
		siftUp(data, top, i)
	}
	// Pop heap.
	for i := last - 1; i >= top; i-- {
		data.Swap(top, i)
		siftDown(data, top, i-1)
	}
}

// heap sort interface.
func HeapSort(data Interface) {
	heapSort(data, 0, data.Len())
}
